{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 模型的评估与选择\n",
    "\n",
    "### 误差与过拟合\n",
    "&emsp;&emsp;我们将学习器对样本的实际预测结果与样本的真实值之间的差异成为：误差（error）。定义：\t\n",
    "\n",
    " - 在训练集上的误差称为训练误差（training error）或经验误差（empirical error）。\n",
    " - 在测试集上的误差称为测试误差（test error）。\n",
    " - 学习器在所有新样本上的误差称为泛化误差（generalization error）。\n",
    "\n",
    "&emsp;&emsp;显然，我们希望得到的是在新样本上表现得很好的学习器，即泛化误差小的学习器。因此，我们应该让学习器尽可能地从训练集中学出普适性的“一般特征”，这样在遇到新样本时才能做出正确的判别。然而，当学习器把训练集学得“太好”的时候，即把一些训练样本的自身特点当做了普遍特征；同时也有学习能力不足的情况，即训练集的基本特征都没有学习出来。我们定义：\n",
    "\n",
    " - 学习能力过强，以至于把训练样本所包含的不太一般的特性都学到了，称为：过拟合（overfitting）。\n",
    " - 学习能太差，训练样本的一般性质尚未学好，称为：欠拟合（underfitting）。\n",
    "\n",
    "&emsp;&emsp;可以得知：在过拟合问题中，训练误差十分小，但测试误差教大；在欠拟合问题中，训练误差和测试误差都比较大。目前，欠拟合问题比较容易克服，例如增加迭代次数等，但过拟合问题还没有十分好的解决方案，过拟合是机器学习面临的关键障碍。\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/2-1-Over-Fit-and-Under-Fit.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图2.1 过拟合 、欠拟合的直观类比</div></center>\n",
    "\n",
    "### 评估方法\n",
    "&emsp;&emsp;在现实任务中，我们往往有多种算法可供选择，那么我们应该选择哪一个算法才是最适合的呢？如上所述，我们希望得到的是泛化误差小的学习器，理想的解决方案是对模型的泛化误差进行评估，然后选择泛化误差最小的那个学习器。但是，泛化误差指的是模型在所有新样本上的适用能力，我们无法直接获得泛化误差。  \n",
    "&emsp;&emsp;因此，通常我们采用一个“测试集”来测试学习器对新样本的判别能力，然后以“测试集”上的“测试误差”作为“泛化误差”的近似。显然：我们选取的测试集应尽可能与训练集互斥，下面用一个小故事来解释why：  \n",
    "&emsp;&emsp;假设老师出了10 道习题供同学们练习，考试时老师又用同样的这10道题作为试题，可能有的童鞋只会做这10 道题却能得高分，很明显：这个考试成绩并不能有效地反映出真实水平。回到我们的问题上来，我们希望得到泛化性能好的模型，好比希望同学们课程学得好并获得了对所学知识\"举一反三\"的能力；训练样本相当于给同学们练习的习题，测试过程则相当于考试。显然，若测试样本被用作训练了，则得到的将是过于\"乐观\"的估计结果。\n",
    "\n",
    "### 训练集与测试集的划分方法\n",
    "&emsp;&emsp;如上所述：我们希望用一个“测试集”的“测试误差”来作为“泛化误差”的近似，因此我们需要对初始数据集进行有效划分，划分出互斥的“训练集”和“测试集”。下面介绍几种常用的划分方法：\n",
    "\n",
    "#### 留出法\n",
    "&emsp;&emsp;将数据集D划分为两个互斥的集合，一个作为训练集$S$，一个作为测试集$T$，满足$D=S\\cup T$且$S \\cap T = \\emptyset $，常见的划分为：大约$\\text{2/3-4/5}$的样本用作训练，剩下的用作测试。需要注意的是：训练/测试集的划分要尽可能保持数据分布的一致性，以避免由于分布的差异引入额外的偏差，常见的做法是采取分层抽样。同时，由于划分的随机性，单次的留出法结果往往不够稳定，一般要采用若干次随机划分，重复实验取平均值的做法。\n",
    "\n",
    "#### 交叉验证法\n",
    "&emsp;&emsp;将数据集$D$划分为$k$个大小相同的互斥子集，满足$D=D_1\\cup D_2\\cup \\cdots \\cup  D_k, \\quad D_i \\cap D_j= \\emptyset (i \\neq j)$，同样地尽可能保持数据分布的一致性，即采用分层抽样的方法获得这些子集。交叉验证法的思想是：每次用$k-1$个子集的并集作为训练集，余下的那个子集作为测试集，这样就有$K$种训练集/测试集划分的情况，从而可进行$k$次训练和测试，最终返回$k$次测试结果的均值。交叉验证法也称“$k$折交叉验证”，k最常用的取值是10，下图给出了10折交叉验证的示意图。\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/2-2-10-Fold-Ccross-Validation.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图2-2 10折交叉验证示意图</div></center>\n",
    "\n",
    "&emsp;&emsp;与留出法类似，将数据集D划分为$K$个子集的过程具有随机性，因此K折交叉验证通常也要重复$p$次，称为$p$次$k$折交叉验证，常见的是10次10折交叉验证，即进行了100次训练/测试。特殊地当划分的$k$个子集的每个子集中只有一个样本时，称为“留一法”，显然，留一法的评估结果比较准确，但对计算机的消耗也是巨大的。\n",
    "\n",
    "#### 自助法\n",
    "\n",
    "&emsp;&emsp;我们希望评估的是用整个$D$训练出的模型。但在留出法和交叉验证法中，由于保留了一部分样本用于测试，因此实际评估的模型所使用的训练集比$D$小，这必然会引入一些因训练样本规模不同而导致的估计偏差。留一法受训练样本规模变化的影响较小，但计算复杂度又太高了。“自助法”正是解决了这样的问题。  \n",
    "&emsp;&emsp;自助法的基本思想是：给定包含$m$个样本的数据集$D$，每次随机从$D$中挑选一个样本，将其拷贝放入$D'$，然后再将该样本放回初始数据集$D$中，使得该样本在下次采样时仍有可能被采到。重复执行$m$次，就可以得到了包含$m$个样本的数据集$D'$。可以得知在$m$次采样中，样本始终不被采到的概率取极限为：\n",
    "$$\n",
    "\\lim _{m \\rightarrow \\infty}\\left(1-\\frac{1}{m}\\right)^{m} \\rightarrow \\frac{1}{e} \\approx 0.368\n",
    "$$\n",
    "&emsp;&emsp;这样，通过自助采样，初始样本集D中大约有36.8%的样本没有出现在$D'$中，于是可以将$D'$作为训练集，$D-D'$作为测试集。自助法在数据集较小，难以有效划分训练集/测试集时很有用，但由于自助法产生的数据集（随机抽样）改变了初始数据集的分布，因此引入了估计偏差。在初始数据集足够时，留出法和交叉验证法更加常用。\n",
    "\n",
    "#### 调参\n",
    "\n",
    "&emsp;&emsp;大多数学习算法都有些参数(parameter) 需要设定，参数配置不同，学得模型的性能往往有显著差别，这就是通常所说的\"参数调节\"或简称\"调参\" (parameter tuning)。  \n",
    "&emsp;&emsp;学习算法的很多参数是在实数范围内取值，因此，对每种参数取值都训练出模型来是不可行的。常用的做法是：对每个参数选定一个范围和步长$\\lambda $，这样使得学习的过程变得可行。例如：假定算法有3个参数，每个参数仅考虑5个候选值，这样对每一组训练/测试集就有$5 \\times 5 \\times 5= 125$个模型需考察，由此可见：拿下一个参数（即经验值）对于算法人员来说是有多么的happy。  \n",
    "&emsp;&emsp;最后需要注意的是：当选定好模型和调参完成后，我们需要使用初始的数据集D重新训练模型，即让最初划分出来用于评估的测试集也被模型学习，增强模型的学习效果。用上面考试的例子来比喻：就像高中时大家每次考试完，要将考卷的题目消化掉（大多数题目都还是之前没有见过的吧？），这样即使考差了也能开心的玩耍了~。\n",
    "\n",
    "### 性能度量\n",
    "\n",
    "&emsp;&emsp;本篇主要是对第二章剩余知识的理解，包括：性能度量、比较检验和偏差与方差。在上一篇中，我们解决了评估学习器泛化性能的方法，即用测试集的“测试误差”作为“泛化误差”的近似，当我们划分好训练/测试集后，那如何计算“测试误差”呢？这就是性能度量，例如：均方差，错误率等，即“测试误差”的一个评价标准。有了评估方法和性能度量，就可以计算出学习器的“测试误差”，但由于“测试误差”受到很多因素的影响，例如：算法随机性或测试集本身的选择，那如何对两个或多个学习器的性能度量结果做比较呢？这就是比较检验。最后偏差与方差是解释学习器泛化性能的一种重要工具。写到后面发现冗长之后读起来十分没有快感，故本篇主要知识点为性能度量。  \n",
    "&emsp;&emsp;性能度量（performance measure）是衡量模型泛化能力的评价标准，在对比不同模型的能力时，使用不同的性能度量往往会导致不同的评判结果。本节除2.5.1外，其它主要介绍分类模型的性能度量。\n",
    "\n",
    "#### 最常见的性能度量\n",
    "&emsp;&emsp;在回归任务中，即预测连续值的问题，最常用的性能度量是“均方误差”（mean squared error）,很多的经典算法都是采用了MSE作为评价函数，想必大家都十分熟悉。\n",
    "$$E(f ; D)=\\frac{1}{m} \\sum_{i=1}^m \\left(f(x_i)-y_i \\right)^{2}$$&emsp;&emsp;更一般的，对于数据分布$D$和概率密度函数$p(\\cdot)$，均方误差可以描述为$$E(f;D)=\\int_{x \\sim D}(f(x)-y)^{2} p(x)dx$$&emsp;&emsp;在分类任务中，即预测离散值的问题，最常用的是错误率和精度，错误率是分类错误的样本数占样本总数的比例，精度则是分类正确的样本数占样本总数的比例，易知：错误率+精度=1。\n",
    "错误率定义为$$E(f ; D)=\\frac{1}{m} \\sum_{i=1}^m I \\left(f(x_i) \\neq y_i\\right)$$精度则定义为$$\n",
    "\\begin{aligned} acc(f ; D) \n",
    "&=\\frac{1}{m} \\sum_{i=1}^{m}I\\left(f(x_i)=y_i \\right) \\\\ \n",
    "&=1-E(f ; D) \n",
    "\\end{aligned}$$&emsp;&emsp;更一般的，对于数据分布$D$和概率密度函数$p(\\cdot)$，错误率与精度可分别描述为$$\n",
    "E(f;D)=\\int_{x \\sim D}I(f(x) \\neq y) p(x) dx\n",
    "$$\n",
    "\n",
    "#### 查准率/查全率/F1\n",
    "&emsp;&emsp;错误率和精度虽然常用，但不能满足所有的需求，例如：在推荐系统中，我们只关心推送给用户的内容用户是否感兴趣（即查准率），或者说所有用户感兴趣的内容我们推送出来了多少（即查全率）。因此，使用查准/查全率更适合描述这类问题。对于二分类问题，分类结果混淆矩阵与查准/查全率定义如下：\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/2-3-Classification-Result-Obfuscation-Matrix.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图2-3 分类结果混淆矩阵</div></center>\n",
    "\n",
    "查准率$P$和查全率$R$分别定义为$$P=\\frac{TP}{TP+FP} \\\\ R=\\frac{TP}{TP+FN}$$&emsp;&emsp;初次接触时，FN与FP很难正确的理解，按照惯性思维容易把FN理解成：False->Negtive，即将错的预测为错的，这样FN和TN就反了，后来找到一张图，描述得很详细，为方便理解，把这张图也贴在了下边：\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/2-4-Confusion-Matrix-Form-of-Binary-Classification.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图2-4 二元分类的混淆矩阵形式</div></center>\n",
    "\n",
    "&emsp;&emsp;正如天下没有免费的午餐，查准率和查全率是一对矛盾的度量。例如我们想让推送的内容尽可能用户全都感兴趣，那只能推送我们把握高的内容，这样就漏掉了一些用户感兴趣的内容，查全率就低了；如果想让用户感兴趣的内容都被推送，那只有将所有内容都推送上，宁可错杀一千，不可放过一个，这样查准率就很低了。  \n",
    "&emsp;&emsp;“P-R曲线”正是描述查准/查全率变化的曲线，P-R曲线定义如下：根据学习器的预测结果（一般为一个实值或概率）对测试样本进行排序，将最可能是“正例”的样本排在前面，最不可能是“正例”的排在后面，按此顺序逐个把样本作为“正例”进行预测，每次计算出当前的P值和R值，如下图所示：\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/2-5-P-R-Curve-and-Balance-Point.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图2-5 P-R曲线与平衡点示意图</div></center>\n",
    "\n",
    "&emsp;&emsp;P-R曲线如何评估呢？若一个学习器A的P-R曲线被另一个学习器B的P-R曲线完全包住，则称：B的性能优于A。若A和B的曲线发生了交叉，则谁的曲线下的面积大，谁的性能更优。但一般来说，曲线下的面积是很难进行估算的，所以衍生出了“平衡点”（Break-Event Point，简称BEP），即当P=R时的取值，平衡点的取值越高，性能更优。  \n",
    "&emsp;&emsp;P和R指标有时会出现矛盾的情况，这样就需要综合考虑他们，最常见的方法就是F-Measure，又称F-Score。F-Measure是P和R的加权调和平均，即：$$\n",
    "\\frac{1}{F_{\\beta}}=\\frac{1}{1+\\beta^{2}} \\cdot\\left(\\frac{1}{P}+\\frac{\\beta^{2}}{R}\\right) \\\\\n",
    "F_{\\beta}=\\frac{\\left(1+\\beta^{2}\\right) \\times P \\times R}{\\left(\\beta^{2} \\times P\\right)+R}\n",
    "$$&emsp;&emsp;特别地，当β=1时，也就是常见的F1度量，是P和R的调和平均，当F1较高时，模型的性能越好。$$\n",
    "\\frac{1}{F 1}=\\frac{1}{2} \\cdot\\left(\\frac{1}{P}+\\frac{1}{R}\\right) \\\\\n",
    "F1=\\frac{2 \\times P \\times R}{P + R} = \\frac{2 \\times TP}{\\text{样例总数 + TP - TN}}\n",
    "$$&emsp;&emsp;有时候我们会有多个二分类混淆矩阵，例如：多次训练或者在多个数据集上训练，那么估算全局性能的方法有两种，分为宏观和微观。简单理解，宏观就是先算出每个混淆矩阵的P值和R值，然后取得平均P值$\\text{macro-}P$和平均R值$\\text{macro-}R$，在算出$F_\\beta$或$F1$，而微观则是计算出混淆矩阵的平均TP、FP、TN、FN，接着进行计算$P,R$，进而求出$F_\\beta$或$F1$。\n",
    "$$\\text{macro-}P=\\frac{1}{n} \\sum_{i=1}^n P_i \\\\\n",
    "\\text{macro-}R=\\frac{1}{n} \\sum_{i=1}^n R_i \\\\\n",
    "\\text{macro-}F1=\\frac{2 \\times \\text{macro-}P \\times \\text{macro-}R}{\\text{macro-}P + \\text{macro-}R} \\\\\n",
    "\\text{micro-}P=\\frac{\\overline{T P}}{\\overline{T P}+\\overline{F P}} \\\\\n",
    "\\text{micro-}R=\\frac{\\overline{T P}}{\\overline{T P}+\\overline{F N}} \\\\\n",
    "\\text{micro-}F1=\\frac{2 \\times \\text{micro-}P \\times \\text{micro-}R}{\\text{micro-}P + \\text{micro-}R}\n",
    "$$\n",
    "\n",
    "#### ROC与AUC\n",
    "&emsp;&emsp;如上所述：学习器对测试样本的评估结果一般为一个实值或概率，设定一个阈值，大于阈值为正例，小于阈值为负例，因此这个实值的好坏直接决定了学习器的泛化性能，若将这些实值排序，则排序的好坏决定了学习器的性能高低。ROC曲线正是从这个角度出发来研究学习器的泛化性能，ROC曲线与P-R曲线十分类似，都是按照排序的顺序逐一按照正例预测，不同的是ROC曲线以“真正例率”（True Positive Rate，简称TPR）为横轴，纵轴为“假正例率”（False Positive Rate，简称FPR），ROC偏重研究基于测试样本评估值的排序好坏。$$\\text{TPR}=\\frac{TP}{TP+FN} \\\\ \n",
    "\\text{FPR}=\\frac{FP}{TP+FP} $$\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/2-6-ROC-and-AUC.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图2-6 ROC 曲线与 AUC 示意图</div></center>\n",
    "\n",
    "&emsp;&emsp;简单分析图像，可以得知：当FN=0时，TN也必须0，反之也成立，我们可以画一个队列，试着使用不同的截断点（即阈值）去分割队列，来分析曲线的形状，（0,0）表示将所有的样本预测为负例，（1,1）则表示将所有的样本预测为正例，（0,1）表示正例全部出现在负例之前的理想情况，（1,0）则表示负例全部出现在正例之前的最差情况。限于篇幅，这里不再论述。  \n",
    "&emsp;&emsp;现实中的任务通常都是有限个测试样本，因此只能绘制出近似ROC曲线。绘制方法：首先根据测试样本的评估值对测试样本排序，接着按照以下规则进行绘制。  \n",
    "> &emsp;&emsp;绘制出如图所示的近似ROC曲线，绘图过程很简单:给定$m^{+}$个正例和$m^{-}$个反例，根据学习器预测结果对样例进行排序，然后把分类阈值设为最大，即把所有样例均预测为反例，此时真正例率和假正例率均为0，在坐标(0,0)处标记一个点，然后，将分类阈值依次设为每个样例的预测值，即依次将每个样例划分为正例。设前一个标记点坐标为$(x,y)$，当前若为真正例，则对应标记点的坐标为$(x,y+\\frac{1}{m^{+}})$；当前若为假正例，则对应标记点的坐标为$(x,y+\\frac{1}{m^{-}})$，然后用线段连接相邻点即得。\n",
    "\n",
    "&emsp;&emsp;同样地，进行模型的性能比较时，若一个学习器A的ROC曲线被另一个学习器B的ROC曲线完全包住，则称B的性能优于A。若A和B的曲线发生了交叉，则谁的曲线下的面积大，谁的性能更优。ROC曲线下的面积定义为AUC（Area Under ROC Curve），不同于P-R的是，这里的AUC是可估算的，即AOC曲线下每一个小矩形的面积之和。易知：AUC越大，证明排序的质量越好，AUC为1时，证明所有正例排在了负例的前面，AUC为0时，所有的负例排在了正例的前面。$$\\text{AUC}=\\frac{1}{2}\\sum_{i=1}^{m-1} (x_{i+1}-x_i) \\cdot (y_i + y_{i+1})$$\n",
    "\n",
    "#### 代价敏感错误率与代价曲线\n",
    "&emsp;&emsp;上面的方法中，将学习器的犯错同等对待，但在现实生活中，将正例预测成假例与将假例预测成正例的代价常常是不一样的，例如：将无疾病-->有疾病只是增多了检查，但有疾病-->无疾病却是增加了生命危险。以二分类为例，由此引入了“代价矩阵”（cost matrix）。\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/2-7-Bicategorized-Cost-Matrix.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图2-7 二分类代价矩阵</div></center>\n",
    "\n",
    "&emsp;&emsp;在非均等错误代价下，我们希望的是最小化“总体代价”，这样“代价敏感”的错误率（2.5.1节介绍）为：$$\n",
    "E(f ; D ; cost)=\\frac{1}{m}\\left(\\sum_{x_i \\in D^{+}} I\\left(f(x_i) \\neq y_i \\right) \\times cost_{01}+\\sum_{x_i \\in D^{-}} I\\left(f(x_i) \\neq y_i \\right) \\times cost_{10} \\right)\n",
    "$$&emsp;&emsp;同样对于ROC曲线，在非均等错误代价下，演变成了“代价曲线”，代价曲线横轴是取值在$[0,1]$之间的正例概率代价，式中p表示正例的概率，纵轴是取值为$[0,1]$的归一化代价。\n",
    "$$\n",
    "P(+) cost=\\frac{p \\times cost_{01}}{p \\times cost_{01}+(1-p) \\times cost_{10}} \\\\\n",
    "cost_{norm}=\\frac{\\text{FNR} \\times p \\times cost_{01}+\\text{FPR} \\times (1-p) \\times cost_{10}}{p \\times cost_{01}+(1-p) \\times cost_{10}}\n",
    "$$&emsp;&emsp;代价曲线的绘制很简单：设ROC曲线上一点的坐标为(TPR，FPR) ，则可相应计算出FNR，然后在代价平面上绘制一条从(0，FPR) 到(1，FNR) 的线段，线段下的面积即表示了该条件下的期望总体代价；如此将ROC 曲线土的每个点转化为代价平面上的一条线段，然后取所有线段的下界，围成的面积即为在所有条件下学习器的期望总体代价，如图所示：\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/2-8-Cost-Curve-and-Expected-Total-Cost.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图2-8 代价曲线与期望总体代价</div></center>\n",
    "\n",
    "&emsp;&emsp;在此模型的性能度量方法就介绍完了，以前一直以为均方误差和精准度就可以了，现在才发现天空如此广阔~  \n",
    "\n",
    "### 比较检验\n",
    "&emsp;&emsp;在上两篇中，我们介绍了多种常见的评估方法和性能度量标准，这样我们就可以根据数据集以及模型任务的特征，选择出最合适的评估和性能度量方法来计算出学习器的“测试误差“。但由于“测试误差”受到很多因素的影响，例如：算法随机性(例如常见的K-Means)或测试集本身的选择，使得同一模型每次得到的结果不尽相同，同时测试误差是作为泛化误差的近似，并不能代表学习器真实的泛化性能，那如何对单个或多个学习器在不同或相同测试集上的性能度量结果做比较呢？这就是比较检验。最后偏差与方差是解释学习器泛化性能的一种重要工具。本篇延续上一篇的内容，主要讨论了比较检验、方差与偏差。  \n",
    "&emsp;&emsp;在比较学习器泛化性能的过程中，统计假设检验（hypothesis test）为学习器性能比较提供了重要依据，即若A在某测试集上的性能优于B，那A学习器比B好的把握有多大。为方便论述，本篇中都是以“错误率”作为性能度量的标准。\n",
    "\n",
    "#### 假设检验\n",
    "&emsp;&emsp;“假设”指的是对样本总体的分布或已知分布中某个参数值的一种猜想，例如：假设总体服从泊松分布，或假设正态总体的期望$\\mu=\\mu_0$。回到本篇中，我们可以通过测试获得测试错误率，但直观上测试错误率和泛化错误率相差不会太远，因此可以通过测试错误率来推测泛化错误率的分布，这就是一种假设检验。\n",
    "&emsp;&emsp;泛化错误率为$\\epsilon$的学习器在一个样本上犯错的概率是 $\\epsilon$；测试错误率$\\hat{\\epsilon}$意味着在$m$个测试样本中恰有三 $\\hat{\\epsilon} \\times m$个被误分类。假定测试样本是从样本总体分布中独立采样而得，那么泛化错误率为$\\epsilon$的学习器将其中$m'$个样本误分类、其余样本全部分类正确的概率是$\\epsilon^{m'}(1-\\epsilon)^{m=m'}$；由此可估算出其恰将 $\\hat{\\epsilon} \\times m$个样本误分类的概率如下式所示，这也表达了在包含$m$个样本的测试集上， 泛化错误率为$\\epsilon$的学习器被测得测试错误率为$\\hat{\\epsilon}$的概率:$$\n",
    "P(\\hat{\\epsilon} ; \\epsilon)=\\left(\\begin{array}{c}{m} \\\\ {\\hat{\\epsilon} \\times m}\\end{array}\\right) \\epsilon^{\\hat{\\epsilon} \\times m}(1-\\epsilon)^{m-\\hat{\\epsilon} \\times m}\n",
    "$$&emsp;&emsp;从上式可以看出，当给定泛化错误率后，测试错误率与样本数的乘积（即测试错误率）就是一个典型的二项分布。因此这里使用二项检验的方法（Binomial Test），现假设$H_0:\\varepsilon \\leqslant \\varepsilon_0, H_1: \\varepsilon > \\varepsilon_0$，即右边检验，因此我们需要讨论单边检验的拒绝域形式，当$H_1$为真时，测试错误率往往偏大，所以拒绝域的形式为$\\hat{\\varepsilon} \\geqslant k$，$k$为某一个正常数。$$P_{\\varepsilon \\in H_0}\\{\\hat{\\varepsilon} \\geqslant k\\} = \\sum_{i=\\lceil mk \\rceil}^m \\left(\\begin{array}{c}{m} \\\\ {i} \\end{array} \\right) \\varepsilon^i (1-\\varepsilon)^{m-i} \\leqslant \\sum_{i=\\lceil mk \\rceil}^m \\left(\\begin{array}{c}{m} \\\\ {i} \\end{array} \\right) \\varepsilon_0^i (1-\\varepsilon_0)^{m-i} \\leqslant \\alpha$$&emsp;&emsp;一般来说，$\\alpha$通常取值为0.01、0.05或0.1，通过该等式从而可以球出去满足条件的$k$值，即临界点，进一步求出该假设检验的拒绝域，当测试错误率大于该临界点时，假设被拒绝。\n",
    "\n",
    "- 在假设检验中，我们称$\\alpha$为显著性水平，也称显著度（significance）\n",
    "- 称$(1-\\alpha)$为置信度（confidence）。\n",
    "\n",
    "&emsp;&emsp;在很多时候，我们会进行多次重复训练，会得到多个测试错误率，假设有$k$个。这时我们可以使用“t检验”，实际上$k$个测试错误率可以看为泛化错误率的$k$次独立采样，因此可以算出这$k$的样本的均值$\\overline{X}$与方差$S^2$。$$\\overline{X}=\\frac{1}{k}\\sum_{i=1}^k \\hat{\\varepsilon}_i, S^2 = \\frac{1}{k-1} \\sum_{i=1}^k(\\hat{\\varepsilon}_i - \\overline{X})^2$$&emsp;&emsp;根据中心极限定理的经典推论，可以得知：$\\displaystyle \\frac{\\overline{X}-\\varepsilon}{S / \\sqrt{n}} \\sim t(n-1)$，当$n$足够大时，$t$分布近似于$N(0,1)$分布，一般情况下在$n > 45$时，就可以使用标准正态分布的上的点的$\\alpha$值，有了这个分布之后，我们就可以类似二项检验进行$t$假设检验。$t$分布的示意图以及常用双边临界值表如下所示：\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/2-9-T-Distribution.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图2-9 $t$分布示意图 $(k = 10)$</div></center>\n",
    "\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/2-10-Common-Critical-Values-of-Bilateral-T-Test.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图2-10 双边$t$检验的常用临界值</div></center>\n",
    "\n",
    "#### 交叉验证t检验\n",
    "&emsp;&emsp;上面我们是对单个学习器的泛化性能进行假设检验，若现在想比较两个学习器A和B的泛化性能，则使用“成对t检验”（paired t-tests）进行比较检验。基本思想是：当对两个学习器进行$k$折交叉验证时，在相同的一组训练/测试集上，学习A/B会产生一对测试错误率$\\hat{\\varepsilon}_A / \\hat{\\varepsilon}_B$，若两个学习器性能相同，则$\\hat{\\varepsilon}_A = \\hat{\\varepsilon}_B$。我们对每一组测试错误率求差值$\\triangle = \\hat{\\varepsilon}_A - \\hat{\\varepsilon}_B$，则可以得到$k$个差值，这$k$个差值可以看做学习器A和学习器B性能差值的独立采样，因此有$$\\frac{\\left|\\overline{\\triangle}-(\\hat{\\varepsilon}_A - \\hat{\\varepsilon}_B)\\right|}{S / \\sqrt{k}} \\sim t(k-1)$$&emsp;&emsp;若假设$H_0:\\varepsilon_A = \\varepsilon_B, H_1:\\varepsilon_A \\neq \\varepsilon_B$，则需满足$\\frac{|\\overline{\\triangle}|}{S / \\sqrt{k}} \\leqslant t_{\\alpha / 2}$，从而求出临界点与拒绝域，与上一节类似，不再赘述。在“成对t检验”的基本思想中，我们的前提是测试错误率是泛化错误率的独立采样，但是在$k$折交叉验证中，选择的训练/测试集难免会产生重叠，因此好的解决办法是使用5次2折交叉验证[Dietterich,1998]，使用第一次的两对差值计算均值，使用全部的差值对（即10对）计算方差，可以有效地避免这个问题。\n",
    "\n",
    "### McNemar检验\n",
    "&emsp;&emsp;McNemar主要用于二分类问题，与成对t检验一样也是用于比较两个学习器的性能大小。主要思想是：若两学习器的性能相同，则A预测正确B预测错误数应等于B预测错误A预测正确数，即$e_{01}=e_{10}$，且$|e_{01}-e_{10}|$服从$N(1，e_{01}+e_{10})$分布。\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/2-11-Two-Learner-Classification-Difference.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图2-11 两学习器分类差别列联表</div></center>\n",
    "\n",
    "&emsp;&emsp;因此，如下所示的变量服从自由度为1的卡方分布，即服从标准正态分布$N(0,1)$的随机变量的平方和，下式只有一个变量，故自由度为1，检验的方法同上：做出假设$\\rightarrow$求出满足显著度的临界点$\\rightarrow$给出拒绝域$\\rightarrow$验证假设。\n",
    "$$\n",
    "\\tau_{\\chi^{2}}=\\frac{\\left(|e_{01}-e_{10}|-1\\right)^{2}}{e_{01}+e_{10}}\n",
    "$$\n",
    "\n",
    "#### Friedman检验与Nemenyi后续检验\n",
    "&emsp;&emsp;上述的三种检验都只能在一组数据集上，F检验则可以在多组数据集进行多个学习器性能的比较，基本思想是在同一组数据集上，根据测试结果（例：测试错误率）对学习器的性能进行排序，赋予序值1,2,3...，相同则平分序值，如下图所示：\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/2-12-Algorithmic-Comparison-Ordinal-Table.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图2-12 算法比较序值表</div></center>\n",
    "\n",
    "&emsp;&emsp;若学习器的性能相同，则它们的平均序值应该相同，且第$i$个算法的平均序值$r_i$服从正态分布$N\\left((k + 1)/2, (k^2-1)/12)\\right)$，则有：$$\n",
    "\\begin{aligned} \\tau_{\\chi^{2}} &=\\frac{k-1}{k} \\cdot \\frac{12 N}{k^2-1} \\sum_{i=1}^k\\left(r_i-\\frac{k+1}{2}\\right)^2 \\\\ \n",
    "&= \\frac{12 N}{k(k+1)}\\left(\\sum_{i=1}^k r_i^2-\\frac{k(k+1)^2}{4}\\right) \\end{aligned}\n",
    "$$在$k$和$N$都比较大时，服从自由度为$k-1$的$\\chi^2$分布。$$\n",
    "\\tau_F=\\frac{(N-1) \\tau_{\\chi^2}}{N(k-1)-\\tau_{\\chi^2}}\n",
    "$$&emsp;&emsp;服从自由度为$k-1$和$(k-1)(N-1)$的$F$分布。下面是$F$检验常用的临界值：\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/2-13-Common-Critical-Values-of-F-Test.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图2-13 $F$ 检验的常用临界值</div></center>\n",
    "\n",
    "&emsp;&emsp;若“$H_0$：所有算法的性能相同”这个假设被拒绝，则需要进行后续检验，来得到具体的算法之间的差异。常用的就是Nemenyi后续检验。Nemenyi检验计算出平均序值差别的临界值域，下表是常用的$q_\\alpha$值，若两个算法的平均序值差超出了临界值域$CD$，则相应的置信度$1-\\alpha$拒绝“两个算法性能相同”的假设。$$CD=q_\\alpha \\sqrt{\\frac{k(k+1)}{6N}}$$\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/2-14-Common-Q-A-Values-of-Nemenyi-Test.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图2-14 Nemenyi 检验中常用的$q_\\alpha$值</div></center>\n",
    "\n",
    "### 偏差与方差\n",
    "&emsp;&emsp;偏差-方差分解是解释学习器泛化性能的重要工具。在学习算法中，偏差指的是预测的期望值与真实值的偏差，方差则是每一次预测值与预测值得期望之间的差均方。实际上，偏差体现了学习器预测的准确度，而方差体现了学习器预测的稳定性。通过对泛化误差的进行分解，可以得到：\n",
    "\n",
    " - 期望泛化误差=方差+偏差\t\n",
    " - 偏差刻画学习器的拟合能力\n",
    " - 方差体现学习器的稳定性\n",
    "\n",
    "&emsp;&emsp;易知：方差和偏差具有矛盾性，这就是常说的偏差-方差窘境（bias-variance dilamma），随着训练程度的提升，期望预测值与真实值之间的差异越来越小，即偏差越来越小，但是另一方面，随着训练程度加大，学习算法对数据集的波动越来越敏感，方差值越来越大。换句话说：在欠拟合时，偏差主导泛化误差，而训练到一定程度后，偏差越来越小，方差主导了泛化误差。因此训练也不要贪杯，适度辄止。\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/2-15-Generalization-Error-and-Bias-and-Variance.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图2-15 泛化误差与偏差、方差的关系示意图</div></center>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
